#include <iterator>
#include <memory>
#include <iostream>
#include <new>
#include <utility>


using __rb_tree_color_type = bool;
const __rb_tree_color_type __rb_tree_red = false;
const __rb_tree_color_type __rb_tree_black = true;

struct __rb_tree_node_base
{
    using color_type = __rb_tree_color_type;
    using base_ptr = __rb_tree_node_base*;

    color_type color;  //
    base_ptr parent;
    base_ptr left;
    base_ptr right;

    static base_ptr minimum(base_ptr x)
    {
        while(x->left != nullptr)
            x = x->left;
        return x;
    }

    static base_ptr maximum(base_ptr x)
    {
        while(x->right != nullptr)
            x = x->right;
        return x;
    }
};

template<typename Value>
struct __rb_tree_node : public __rb_tree_node_base
{
    using link_type = __rb_tree_node<Value>*;
    Value value_field;
};

struct __rb_tree_base_iterator
{
    using base_ptr = __rb_tree_node_base::base_ptr;
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;

    // Iterator point to a node in rb-tree
    base_ptr node;

    void increment()
    {
        // 右子树非空，那么就是右子树最左下的结点
        if(node->right != nullptr)
        {
            node = node->right;
            while(node->left != nullptr)
                node = node->left;
        }
        // 右子树为空，是父亲的左孩子：那么下个结点就是父亲，是父亲的右孩子，不断往上找
        else
        {
            base_ptr y = node->parent;
            // 当前Node是一个右孩子，那么就不断往上走，直到不是父亲y的右孩子为止
            while(node == y->right)
            {
                node = y;
                y = y->parent;
            }
            // 是父亲的左孩子，那么下个结点就是父亲
            // 这里的判断是为了一种特殊情况
            if(node->right != y)
                node = y;
        }
    }

    void decrement()
    {
        // 整颗树中仅有唯一一个结点的情况
        if(node->color == __rb_tree_red && node->parent->parent == node)
            node = node->right;
        // 左子树非空的情况：那么就是左子树最右下的结点
        else if(node->left != nullptr)
        {
            base_ptr y = node->left;
            while(y->right != nullptr)
                y = y->right;
            node = y;
        }
        // 左子树为空了，那么一直交替往上走，直到当前node不是父亲的左孩子，此时父亲便是答案
        else
        {
            base_ptr y = node->parent;
            while(node == y->left)
            {
                node = y;
                y = y->parent;
            }
            node = y;
        }
    }

};

template<typename Value, typename Ref, typename Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
    using value_type = Value;
    using reference = Ref;
    using pointer = Ptr;
    using iterator = __rb_tree_iterator<Value, Ref&, Ptr*>;
    using const_iterator = __rb_tree_iterator<Value, const Ref&, const Ptr*>;
    using self = __rb_tree_iterator<Value, Ref, Ptr>;
    using link_type = __rb_tree_node<Value>*;

    __rb_tree_iterator() = default;
    // link_type 是 __rb_tree_node<Value>* 类型
    // node 是 __rb_tree_node_base* 类型

    // 这里不能用__rb_tree_iterator(link_type x) : node(x) {}
    // 因为这里会先调用父类构造函数构造了一个node才可以在这里的构造函数里赋值
    __rb_tree_iterator(link_type x) : __rb_tree_base_iterator(x) {}
    __rb_tree_iterator(const iterator& it)  {node = it.node;}
    
    reference operator*() const 
    {
        // 父类指针强转为子类指针
        return link_type(node)->value_field;
    }

    pointer operator->() const 
    {
        return &(operator*());
    }

    self& operator++()
    {
        increment();
        return *this;
    }

    self operator++(int)
    {
        self tmp = *this;
        increment();
        return tmp;
    }

    self& operator--()
    {
        decrement();
        return *this;
    }

    self operator--(int)
    {
        self tmp = *this;
        decrement();
        return tmp;
    }
};

// -------------- Inline Function ------------------
inline void __rb_tree_rotate_left(
    __rb_tree_node_base* x,
    __rb_tree_node_base*& root
)
{
    __rb_tree_node_base* y = x->right;
    x->right = y->left;
    if(y->left != nullptr)
        y->left->parent = x;
    y->parent = x->parent;

    if(x == root)
        root = y;
    else if(x == x->parent->left)
        x->parent->left = y;
    else
        x->parent->right = y;
    y->left = x;
    x->parent = y;
};

inline void __rb_tree_rotate_right
(
    __rb_tree_node_base* x,
    __rb_tree_node_base*& root
)
{
    __rb_tree_node_base* y = x->left;
    x->left = y->right;
    if(y->left != nullptr)
        y->right->parent = x;
    y->parent = x->parent;

    if(x == root)
        root = y;
    else if(x == x->parent->right)
        x->parent->right = y;
    else
        x->parent->left = y;
    y->right = x;
    x->parent = y;
}

template<typename Key, typename Value, typename KeyOfValue, typename Compare, 
typename Alloc = std::allocator<Value>>
class rb_tree
{
    protected:
    using void_pointer = void*;
    using base_ptr = __rb_tree_node_base*;
    using rb_tree_node = __rb_tree_node<Value>;
    using rb_tree_node_allocator = Alloc;
    using color_type = __rb_tree_color_type;

    public:
    using key_type = Key;
    using value_type = Value;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reference = value_type&;
    using const_reference = const value_type&;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using link_type = __rb_tree_node<Value>*;

    protected:
    link_type get_node()
    {
        // 调用rb_tree_node_allocator::allocate()分配一个node返回一个地址转为一个指针
        return rb_tree_node_allocator::allocate();
    }

    void put_node(link_type p)
    {
        return rb_tree_node_allocator::deallocate(p);
    }

    link_type create_node(const value_type& value)
    {
        link_type tmp = get_node();
        try
        {
            // C++ 20
            // std::construct_at(&tmp->value_field, value);
            ::new (static_cast<void*>(tmp)) link_type(value);
        }
        catch(const std::exception& e)
        {
            std::cout << "std::construct_at failed : " << e.what() << std::endl;
            put_node(tmp);
            tmp = nullptr;
        }
        return tmp;
    }

    link_type clone_node(link_type x)
    {
        link_type tmp = create_node(x->value_field);
        tmp->color = x->color;
        tmp->left = nullptr;
        tmp->right = nullptr;
        return tmp;
    }

    void destroy_node(link_type p)
    {
        std::destroy_at(&p->value_field);
        put_node(p);
    }

    protected:
    // node-count : 用于记录树的大小
    size_type node_count;
    link_type header;
    Compare key_compare;

    // 方便取得header成员
    link_type& root() const
    {
        // header -> parent = root
        return static_cast<link_type&>(header->parent);
    }
    link_type& leftmost() const
    {
        return static_cast<link_type&>(header->left);
    }
    link_type& rightmost() const
    {
        return static_cast<link_type&>(header->right);
    }

    // 取得结点X的成员
    static link_type& left(link_type x)
    {
        return static_cast<link_type&>(x->left);
    }   
    static link_type& right(link_type x)
    {
        return static_cast<link_type&>(x->right);
    }
    static link_type& parent(link_type x)
    {
        return static_cast<link_type&>(x->parent);        
    }
    static reference value(link_type x)
    {
        return x->value_field;
    }
    static const Key& key(link_type x)
    {
        // 调用KeyOfValue的operator()参数为value(x)
        return KeyOfValue()(value(x));
    }
    static color_type& color(link_type x)
    {
        return static_cast<color_type&>(x->color);
    }
     static link_type& left(base_ptr x)
    {
        return static_cast<link_type&>(x->left);
    }   
    static link_type& right(base_ptr x)
    {
        return static_cast<link_type&>(x->right);
    }
    static link_type& parent(base_ptr x)
    {
        return static_cast<link_type&>(x->parent);        
    }
    static reference value(base_ptr x)
    {
        return static_cast<link_type&>(x)->value_field;
    }
    static const Key& key(base_ptr x)
    {
        // 调用KeyOfValue的operator()参数为value(x)
        return KeyOfValue()(value(link_type(x)));
    }
    static color_type& color(base_ptr x)
    {
        return static_cast<color_type&>(x->color);
    }

    // 求树的极大和极小值
    static link_type minimum(link_type x)
    {
        return static_cast<link_type>(
            __rb_tree_node_base::minimum(x)
        );
    }

    static link_type maximum(link_type x)
    {
        return static_cast<link_type>(
            __rb_tree_node_base::maximum(x)
        );
    }

    public:
    using iterator = __rb_tree_iterator<Value, reference, pointer>;

    private:
    iterator __insert(base_ptr x, base_ptr y, const value_type& v);
    link_type __copy(link_type x, link_type p);
    void __erase(link_type x);
    void clear();
    void init()
    {
        header = get_node();
        header->color = __rb_tree_red;
        // header->parent = nullptr;
        root() = nullptr;
        // header->left = header
        leftmost() = header;
        // header->right = header;
        rightmost() = header;
    }

    public:
    // constructor
    rb_tree(
        const Compare& comp = Compare()
    ) : node_count(0), key_compare(comp)
    {
        // set header
        init();
    }

    ~rb_tree()
    {
        // clear wait to implementation
        clear();
        put_node(header);
    }

    rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& operator=(
        const rb_tree<Key, Value, KeyOfValue, Compare, Alloc>& x
    );

    public:
    Compare key_comp() const
    {
        return key_compare;
    }

    // RB-tree 的起点为最左结点
    iterator begin()
    {
        return leftmost();
    }

    // RB树的终点为header
    iterator end()
    {
        return header;
    }

    bool empty() const
    {
        return node_count == 0;
    }

    size_type size() const
    {
        return node_count;
    }

    size_type max_size() const
    {
        return std::numeric_limits<size_type>::max() / sizeof(rb_tree_node);
    }

    public:
    // 将x插入到RB-tree中，保持结点的独一无二
    std::pair<iterator, bool> insert_unique(const value_type& v);
    // 将x插入到RB-tree中，允许重复
    iterator insert_equal(const value_type& v);
};

template<typename Key, typename Value, typename KeyOfValue,
typename Compare, typename Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_equal(
    const Value& v
)
{
    link_type y = header;
    link_type x = root();
    while(x != nullptr)
    {
        y = x;
        // KeyOfValue 实例化一个取值函数，从value取出其key值
        // 这个类型一定要重载了operator()
        // key_compare是一个Funtor返回一个bool值
        // 遇到大值往左走，遇到小值等于往右走

        x = key_compare(
            KeyOfValue()(v), key(x)
        ) ? left(x) : right(x) ;
    }
    // x是插入点迭代器，y是x的父亲
    return __insert(x, y, value);
}

template<typename Key, typename Value, typename KeyOfValue,
typename Compare, typename Alloc>
std::pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(
    const Value& v
)
{
    link_type y = header;
    link_type x = root();
    bool comp = true;
    while(x != nullptr)
    {
        y = x;
        // comp 记录v的键值小于当前结点的键值
        comp = key_compare(
            KeyOfValue()(v), key(x)
        );
        x = comp ? left(x) : right(x);
    }
    // 令迭代器j指向插入点之父节点y
    iterator j = iterator(y);
    // 如果离开while时候comp为真，遇大，应该插入左侧
    if(comp)
    {
        // 插入点的父节点为树的最左结点,此时直接插入，不需要检查
        if(j == begin())
            return std::pair<iterator, bool>(
            __insert(x, y, v), true
            );
        else
        /*
        --j 用于将迭代器 j 回退到当前父节点 y 的前驱节点。
        这个操作是为了检查待插入的键值是否与前驱节点的键值相同
        */
            --j;
    }
    // keycompare(a, b) : true -> a < b
    // 比较父亲y的键值是否要小于插入点，为真则插入右边
    if(key_compare(key(j.node), KeyOfValue()(v)))
        return std::pair<iterator, bool>(
            __insert(x, y, v), true
        );
    // 大于和小于情况都比较结束了，只有一种可能就是等于
    return std::pair<iterator, bool>(j, false);
}

template<typename Key, typename Value, typename KeyOfValue,
typename Compare, typename Alloc>
typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator
rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__insert(
    base_ptr x_, base_ptr y_, const Value& v
)
{
 // X_ 为新插入点， y_ 为插入点的父节点，v为新
    link_type x = link_type(x_);
    link_type y = link_type(y_);
    link_type z;

    // 如果树中没有结点，或者是插在左边的情况
    if(y == header || x!= nullptr || 
    key_compare(KeyOfValue()(v), key(y)))
    {
        z = create_node(v);
        left(y) = z;
        if(y == header)
        {
            root() = z;
            rightmost() = z;
        }
        else if(y == leftmost())
            leftmost() = z;
        // 1 . 情况一 ： y == header : z作为新节点插入，分别执行了 : z = create_node(v) ; left(y) = z; root() = z; rightmost() = z
        // 2 . 情况二 ： y == leftmost() : 是中序遍历最前之前插入，分别执行了 : z=create_node(v);left(y)=z;leftmost()=z
    }   
    else
    {
        // 插在右边的情况
        z = create_node(v);
        right(y) = z;
        if(y == rightmost())
            rightmost() = z;
        // y == header 情况已经在上面处理过了
        // 只有y == rightmost() 情况了
    }
    // 在这里统一设置z的指针
    parent(z) = y;
    left(z) = nullptr;
    right(z) = nullptr;

    // 重新把树调整平衡
    __rb_tree_rebalance(z, header->parent);
    ++node_count;
    return iterator(z);
}

// param 1 : insert node
// param 2 : root node
// 这里把LL和LR合一起，RL和RR合一起。LR多一步左旋，RL多一步右旋
inline void __rb_tree_rebalance(
    __rb_tree_node_base* x,
    __rb_tree_node_base*& root
)
{
    // 只可能会被破坏了两个相同的红节点这个规则
    // 新插入结点为红色
    x->color = __rb_tree_red;
    // 当前插入结点的父节点也是红色
    while(x != root && x->parent->color == __rb_tree_red)
    {
        // 父结点为爷结点的左孩子
        if(x->parent = x->parent->parent->left)
        {
            // y 为叔叔结点
            __rb_tree_node_base* y = x->parent->parent->right;
            // 红叔叔
            if(y && y->color ==  __rb_tree_red)
            {
                // 叔父爷同时变色，爷爷结点变为新节点以递归调整
                x->parent->color == __rb_tree_black;
                y->color = __rb_tree_black;
                // 自己为红，父亲为黑叔叔为黑，爷爷只能是红
                x->parent->parent->color = __rb_tree_red;
                // 递归调整 : 爷变新
                x = x->parent->parent;
            }
            // 没有叔叔结点（即叔叔是黑的），或者是有叔叔，叔叔是黑的
            else
            {
                if(x == x->parent->right)
                {
                    // 即黑叔叔。并且是LR型不平衡：左右双旋，儿子换爷爷，两者变色
                    x = x->parent;
                    // 左旋点为插入点的父亲，即x->parent, 第二参数为根
                    __rb_tree_rotate_left(x, root);
                }
                // 上面的__rb_tree_rotate_left(x, root)执行后，x应该还是指向了新节点x
                // 无论是x == x->parent->right还是x == x->parent->left都要执行
                x->parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_right(x->parent->parent, root);
            }
        }
        //  父结点为爷结点的右孩子
        else
        {
            // 叔叔
            __rb_tree_node_base* y = x->parent->parent->left;
            if(y && y->color == __rb_tree_red)
            {
                // 红叔叔
                // 叔父爷染色，爷变新
                x->parent->color = __rb_tree_black;
                y->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                x = x->parent->parent;
            }
            else
            {
                if(x == x->parent->left)
                {
                    x = x->parent;
                    __rb_tree_rotate_right(x, root);
                }
                x->parent->color = __rb_tree_black;
                x->parent->parent->color = __rb_tree_red;
                __rb_tree_rotate_left(x->parent->parent, root);
            }
        }
    }
    // 根节点永远为黑色
    root->color = __rb_tree_black;
}

template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::clear()
{
    __erase(root());
    left(header) = header;
    right(header) = header;
    parent(header) = nullptr;
}


template <typename Key, typename Value, typename KeyOfValue, typename Compare, typename Alloc>
void rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::__erase(link_type x)
{
    if (x == nullptr) return;
    __erase(left(x));
    __erase(right(x));
    destroy_node(x);
}